public class Test2 {
    //移除元素
    //给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。
    // 元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
    //输入：nums = [3,2,2,3], val = 3
    //输出：2, nums = [2,2,_,_]
    //解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
    //你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
    //https://leetcode.cn/problems/remove-element/description/
    public static int removeElement2(int[] nums, int val) {
        //双指针法
         int left = 0;
         int right = nums.length;
         while (left < right) {
         if (nums[left] == val) {
         nums[left] = nums[right - 1];
         right--;
         } else {
         left++;
         }
         }
         return left;
    }
    public static int removeElement1(int[] nums, int val) {
        int n = nums.length;
        int[] newNums = new int[n];
        int n1 = 0;
        int n2 = 0;
        int count = 0;
        while(n1 < nums.length) {
            if(nums[n1] != val) {
                newNums[n2++] = nums[n1++];
            }else{
                n1++;
                count++;
            }
        }
        System.arraycopy(newNums,0,nums,0,n);
        return nums.length - count;
    }
    //面试题 消失的数字
    //数组nums包含从0到n的所有整数，但其中缺了一个。
    //请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
    //比如:
    //输入：[3,0,1]
    //输出：2
    //https://leetcode.cn/problems/missing-number-lcci/description/
    public static int missingNumber(int[] nums) {
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            //我们^每一个数字，当^上相同的元素，值就为0，最后的就是我们要得到的元素
            count ^= i;
            count ^= nums[i];
        }//这个循环不能等于nums.length，因为会越界
        count ^= nums.length;//从0-nums.lenght的长度
        return count;
    }

    //轮转数组
    //给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
    //输入: nums = [1,2,3,4,5,6,7], k = 3
    //输出: [5,6,7,1,2,3,4]
    //解释:
    //向右轮转 1 步: [7,1,2,3,4,5,6]
    //向右轮转 2 步: [6,7,1,2,3,4,5]
    //向右轮转 3 步: [5,6,7,1,2,3,4]
    //https://leetcode.cn/problems/rotate-array/description/
    //第一种方法
    public void swap(int[] nums,int i,int j) {
        while(i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
    public void rotate1(int[] nums, int k) {
        k = k % nums.length;//如果k > nums.length 的长度的话，会进行从新调换，
        swap(nums,0,nums.length - 1);//整体进行旋转
        swap(nums,0,k - 1);//左面进行旋转
        swap(nums,k,nums.length - 1);//右面进行旋转
    }
    //第二种方法
    public void rotate2(int[] nums, int k) {
        int length = nums.length;//数组的长度
        //创建一个新的数组
        int[] newNums = new int[length];
        for(int i = 0; i < length; i++) {
            newNums[(i + k) % length] = nums[i];
            //比如我们的0下标的1，这个代码执行后就会到达3下标位置，就是它的最终位置
        }
        System.arraycopy(newNums,0,nums,0,length);
        //把newNums这个数组从零开始拷贝到nums数组中拷贝长度为nums的数组长度
    }

    public void rotate3(int[] nums, int k) {
        //这个代码没有问题，但是时间复杂度会超
        if (nums.length == 1) {
            return;
        }
        k = k % nums.length;
        for (int i = 0; i < k; i++) {
            int endNumber = nums[nums.length - 1];
            for (int j = nums.length - 1; j >= 1 ; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = endNumber;
        }
    }
    public static void main(String[] args) {
//        int[] array = {3,0,1};
//        System.out.println(missingNumber(array));
//        int[] array = {1,2,3,4,5,6,7};
//        rotate1(array,3);
//        rotate2(array,3);
//        int[] array = {3,2,2,3};
//        removeElement1(array,3);
//        removeElement2(array,3);
    }
}
